package baseclass.l_string;

import baseclass.a_sort.Generator;

import java.util.Arrays;

/**
 * 给定数组arr，求数组循环右移k位后的结果。
 * @date 2020/3/5 22:25
 */
public class Code02_数组循环移动K位结果 {
    /**
     * 错误示范：
     * 方式1：全体移动k位。时间O(n)，空间O(1)
     */
    public static void remove1(int[]arr,int k){
        if(arr == null || arr.length ==0 || k <= 0) return;
        int index = 0;
        //如arr = {1,2}  k = 1   第一次for循环，arr = {1,1} 增强for的第二次也会被改变
        //其实就是迭代器的原理，迭代过程不能被改变或删除或新增
        for (int e : arr) { //利用增强for循环，循环和index一一对应。
            int targetIndex = (index + k) % arr.length;
            arr[targetIndex] = e;
            index++;
        }

    }
    public static void remove2(int[]arr,int k) {
        if (arr == null || arr.length == 0 || k <= 0) return;
        int[] copy = Arrays.copyOf(arr, arr.length);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = copy[(i + k) % arr.length];
        }
    }

    /**
     * 方式3：时间O(n),空间O(1)
     * 画示意图：设长度为len，左侧len-k个翻转，右侧k个翻转，然后整体翻转。
     * 如果要求循环左移，左侧翻转k，右侧翻转len-k
     */
    public static void remove3(int[]arr,int k){
        if (arr == null || arr.length == 0 || k <= 0 || arr.length == k) return;
        if(arr.length > k) k = (k & (arr.length -1));
        //len - k  ~  len-1 共k个
        reverse(arr,arr.length - k ,arr.length-1);
        reverse(arr,0,arr.length - k - 1);
        reverse(arr,0,arr.length-1);
    }
    private static void reverse(int[]arr,int i,int j) {
        while (i != j){
            arr[i] = arr[i] ^ arr[j];
            arr[j] = arr[i] ^ arr[j];
            arr[i] = arr[i] ^ arr[j];
            i++;
            j--;
        }
    }

    public static void main(String[] args) {
        int[] ints = Generator.generateRandomArray(5, 50);
        for (int i = 0; i < 100000; i++) {
            int k = (int) (Math.random()*(ints.length+1));
            int[] copy1 = Arrays.copyOf(ints, ints.length);
            int[] copy2 = Arrays.copyOf(ints, ints.length);
            try {
                // remove1(copy2,k);  error
                remove2(copy2,k);
                remove3(copy1,k);
                if(!Arrays.equals(copy1, copy2)){
                    System.out.println("===error===");
                    System.out.println(Arrays.toString(ints));
                    System.out.println("k = " + k);
                    break;
                }
            }catch (Exception e){
                System.out.println(Arrays.toString(ints));
                System.out.println("k = " + k);
                System.out.println("exception");
                System.exit(0);
            }

        }
    }
}
